#!/home/zhangbing/anaconda3/bin/python
# coding=utf-8

import random
import time

CHOOSE_FIRST = 0x0011
CHOOSE_MIDDLE = 0x0012

#quick sort
def quick_sort(arr,mod):
    n = len(arr)
    if n <= 1:
        return arr

    if mod == CHOOSE_FIRST:
        i_mid = 0
    elif mod == CHOOSE_MIDDLE:
        i_mid = int((n + 1)/ 2)
    else:
        i_mid = random.randint(0, n - 1)

    left_list = []
    right_list = []
    middle_list = []

    value_middle = arr[i_mid]

    for i in range(n):
        if arr[i] < value_middle:
            left_list.append(arr[i])
            continue
        if arr[i] > value_middle:
            right_list.append(arr[i])
            continue
        middle_list.append(arr[i])


    return quick_sort(left_list,mod) + middle_list + quick_sort(right_list,mod)

def test_with_mode(test_arr,mod):

    start_time = time.process_time()

    print(test_arr)
    result_arr = quick_sort(test_arr,mod)
    print(result_arr)

    end_time = time.process_time()

    mode_name = "random"

    if mod == CHOOSE_FIRST:
        mode_name = "choose first"
    elif mod == CHOOSE_MIDDLE:
        mode_name = "choose middle"

    print("\r\nmode: " + mode_name +"      time :" + str(end_time - start_time))

def test():
    test_arr = [random.randint(0, 500000) for i in range(30000)]
    test_with_mode(test_arr,CHOOSE_FIRST)
    test_with_mode(test_arr, CHOOSE_MIDDLE)
    test_with_mode(test_arr, 0)

if __name__ == "__main__":
    test()


